package leetcode.primary;

import utils.tree.BinaryTree;
import utils.tree.Tree;
import utils.tree.TreeNode;

public class T124 {
    public int max;
    public int maxPathSum(TreeNode root) {
        max = root.val;
        DFS(root);
        return max;
    }

    public int DFS(TreeNode node){
        if (node==null){
            return 0;
        }
        int leftMax = Math.max(DFS(node.left),0);
        int rightMax = Math.max(DFS(node.right),0);

        int temp = leftMax+rightMax+node.val;
        if (temp>max){
            max = temp;
        }

        return node.val+Math.max(leftMax,rightMax);

    }

    public static void main(String[] args) {
        T124 t124 = new T124();
        Tree tree = new BinaryTree(new int[]{1,-2,0,0,3,0,0});
        TreeNode root = tree.InitTree();
        tree.InorderTravel(root);
        System.out.println();
        int maxPathSum = t124.maxPathSum(root);
        System.out.println(maxPathSum);

    }
}
